#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//int main()
//{
//	string s("abcdef");
//	cout << s << endl;
//	reverse(s.begin() + 2, s.begin() + s.size());
//	cout << s << endl;
//}

//翻转字符串II：区间部分翻转
//https ://leetcode-cn.com/problems/reverse-string-ii/

//class Solution {
//public:
//
//
//    string reverseStr(string s, int k) {
//        for (int i = 0; i < s.size(); i += 2 * k)
//        {
//            //剩余字符大于等于k个翻转前k个
//            if (i + k <= s.size())
//            {
//                reverse(s.begin() + i, s.begin() + i + k);
//                continue;
//            }
//            //剩余字符不足k个，翻转所有剩余字符
//            reverse(s.begin() + i, s.begin() + s.size());
//        }
//        return s;
//    }
//};

//翻转字符串III：翻转字符串中的单词
//https ://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
//class Solution {
//public:
//    string reverseWords(string s) {
//        int front = 0;//记录逆置区间的前下标  
//        int behind = 0;//记录逆置区间的后下标
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == ' ')
//            {
//                behind = i;
//                reverse(s.begin() + front, s.begin() + behind);
//                front = i + 1;
//            }
//        }
//        reverse(s.begin() + front, s.begin() + s.size());
//        return s;
//    }
//};

//字符串相乘
//https ://leetcode-cn.com/problems/multiply-strings/description/

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size();
        int m = num2.size();
        vector<int>A;
        vector<int>B;
        //初始化，倒置存放，低位在低下标。
        for (int i = n - 1; i >= 0; i--)
        {
            A.push_back(num1[i] - '0');
        }
        for (int i = m - 1; i >= 0; i--)
        {
            B.push_back(num2[i] - '0');
        }
        vector<int>C(n + m);
        for (int j = 0; j < m; j++)
        {
            for (int i = 0; i < n; i++)
            {
                C[i + j] += A[i] * B[j];
            }
        }
        //得到优化乘法数组
        int add = 0;//初始化进位
        for (int i = 0; i < C.size(); i++)
        {
            add += C[i];
            C[i] = add % 10;
            add = add / 10;
        }
        int k = C.size() - 1;
        while (k > 0 && !C[k])
        {
            //去除前导0
            k--;
        }
        string res;
        //翻转——反着加
        while (k >= 0)
        {
            res += C[k--] + '0';
        }
        return res;
    }
};